package com.kevin.Code.String;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author Vinlee Xiao
 * @Classname RestoreIpAddresses
 * @Description Leetcode 93 复原IP地址 中等难度
 * @Date 2021/11/13 9:45
 * @Version 1.0
 */
public class RestoreIpAddresses {

    List<String> result = new ArrayList<>();
    int maxValue = Integer.MAX_VALUE;

    /**
     * 首先思路，深度优先遍历
     *
     * @param s
     * @return
     */
    public List<String> restoreIpAddresses(String s) {

        int len = s.length();
        List<String> combiner = new ArrayList<>();
        //最大的字符长度为12
        if (len > 12) {
            return result;
        }
        dfs(s, 0, combiner, 0, len);

        return result;
    }

    /**
     * @param s
     * @param startIndex 下一个开始的坐标
     * @param combiner
     * @param cnt
     * @param len
     */
    private void dfs(String s, int startIndex, List<String> combiner, int cnt, int len) {
        //退出递归循环的条件
        if (cnt > 4) {
            return;
        }

        if (cnt == 4 && startIndex >= len) {
            result.add(combiner.stream().collect(Collectors.joining(".")));
        }

        for (int i = 1; i <= 3; i++) {
            if (i + startIndex > len) {
                continue;
            }
            String sub = s.substring(startIndex, startIndex + i);
            //判断是否出现前导零
            int zeroIndex = maxValue;
            int digitIndex = maxValue;
            boolean isPreZero = false;
            int num = Integer.parseInt(sub);
            if (num >= 0 && num <= 255) {
                //排除含有前导零的子字符串 写法有点冗余
                for (int j = 0; j < sub.length(); j++) {
                    if (sub.charAt(j) == '0') {
                        if (zeroIndex != maxValue && digitIndex > zeroIndex) {

                            isPreZero = true;
                            break;
                        }
                        zeroIndex = j;
                    }
                    if (sub.charAt(j) != '0') {
                        if (zeroIndex < digitIndex) {
                            isPreZero = true;
                            break;
                        }
                        digitIndex = j;

                    }
                }
                if (isPreZero) {
                    continue;
                }
                combiner.add(sub);
                dfs(s, startIndex + i, combiner, cnt + 1, len);
                combiner.remove(combiner.size() - 1);
            }
        }
    }

    public static void main(String[] args) {
        RestoreIpAddresses restoreIpAddresses = new RestoreIpAddresses();
        List<String> list = restoreIpAddresses.restoreIpAddresses("010010");
        for (String s : list) {
            System.out.println(s);
        }
    }
}
